package top100;

import java.util.Arrays;

/**
 * @author Godc
 * @description
 */
public class NextPermutation {
    public static void main(String[] args) {
        NextPermutationSolution s = new NextPermutationSolution();
        s.nextPermutation(new int[]{5,1,1});
    }
}
class NextPermutationSolution {
    public void nextPermutation(int[] nums) {
        if(nums.length==1) return;
        // 1 2 3 5 4
        // 1 2 3 4 5
        // 1 1 5 2 4
        // 7 6 5 3 1
        int i = nums.length-2,j = nums.length-1;
        while(i>=0&&nums[i]>nums[j]){
            i--;
            j--;
        }
        if(i<0)
            reverse(nums,0,nums.length-1);
        else{
            for(int k = nums.length-1;k>=j;k--){
                if(nums[k]>nums[i]){
                    swap(nums,k,i);
                    reverse(nums,i+1,nums.length-1);
                    return;
                }
            }
        }
    }
    public void reverse(int[] nums,int i,int j){
        while(i<j){
            swap(nums,i,j);
            i++;
            j--;
        }
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}